package leetcode.editor.cn.q1_300.q;

/**
 * @author qidi
 * @date 2021-11-19 15:30:35
 */
class Q0042_TrappingRainWater {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int trap(int[] height) {
            if (height.length == 0) return 0;
            int len = height.length;
            int[] arr = new int[len];
            for (int i = 0; i < len; i++) {
                arr[i] = -1;
            }
            int lMax = height[0];
            int rMax = height[len - 1];
            for (int i = 0; i < len; i++) {
                lMax = Math.max(lMax, height[i]);
                int right = len - i - 1;
                rMax = Math.max(rMax, height[right]);
                if (arr[i] == -1 || lMax < arr[i]) {
                    arr[i] = lMax;
                }
                if (arr[right] == -1 || rMax < arr[right]) {
                    arr[right] = rMax;
                }
            }

            int res = 0;
            for (int i = 0; i < len; i++) {
                res += arr[i] > height[i] ? arr[i] - height[i] : 0;
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0042_TrappingRainWater().new Solution();
        System.out.println(solution.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        System.out.println(solution.trap(new int[]{4, 2, 0, 3, 2, 5}));
    }
}